#include<bits/stdc++.h>
using namespace std;
namespace MAOJUN{

const int N=1e5+5,E=4e5+5;
int n,m;
int tot,hd[N],to[E],nxt[E],ew[E];
inline void Add(int u,int v,int w){to[++tot]=v;nxt[tot]=hd[u];hd[u]=tot;ew[tot]=w;}

int K,S;bool vs[N],ins[N];
int mn,mx,ds[N];
void dfs(int u,int ie){
	mn=min(mn,ds[u]);mx=max(mx,ds[u]);
	vs[u]=ins[u]=1;
	for(int i=hd[u];i;i=nxt[i])if(i^ie^1){
		int v=to[i];
		if(!vs[v]){ds[v]=ds[u]+ew[i];dfs(v,i);}
		else if(ins[v]){
			int x=abs(ds[u]-ds[v]+ew[i]);
			if(x)K=K?__gcd(K,x):x;
		}
	}
	ins[u]=0;
}
#define mem(a) memset(a,0,sizeof a)
inline void slv(){
	tot=1;mem(hd);
	scanf("%d%d",&n,&m);
	for(int u,v;m--;){scanf("%d%d",&u,&v);u++;v++;Add(u,v,1);Add(v,u,-1);}
	K=S=0;mem(vs);
	for(int i=1;i<=n;i++)if(!vs[i]){
		mn=mx=ds[i]=0;dfs(i,0);S+=mx-mn;
	}
	printf("%d\n",n-(K?K:S));
}
inline void main(){int T;scanf("%d",&T);while(T--)slv();}

}int main(){
	freopen("circ.in","r",stdin);
	freopen("circ.out","w",stdout);
	MAOJUN::main();
	return 0;
}